package main

// 51. N 皇后
func main() {
	n := 4
	queens := solveNQueens(n)

	for _, permuteNum := range queens {
		for _, num := range permuteNum {
			print(num, ",")
		}
		println()
	}
}

var solutions [][]string

func solveNQueens(n int) [][]string {
	solutions = [][]string{}
	queens := make([]int, n)
	for i := 0; i < n; i++ {
		queens[i] = -1
	}
	columns := map[int]bool{}
	diagonals1, diagonals2 := map[int]bool{}, map[int]bool{}
	backtrack(queens, n, 0, columns, diagonals1, diagonals2)
	return solutions
}

func backtrack(queens []int, n, row int, columns, diagonals1, diagonals2 map[int]bool) {
	if row == n {
		board := generateBoard(queens, n)
		solutions = append(solutions, board)
		return
	}
	for i := 0; i < n; i++ {
		if columns[i] {
			continue
		}
		diagonal1 := row - i
		if diagonals1[diagonal1] {
			continue
		}
		diagonal2 := row + i
		if diagonals2[diagonal2] {
			continue
		}
		queens[row] = i
		columns[i] = true
		diagonals1[diagonal1], diagonals2[diagonal2] = true, true
		backtrack(queens, n, row+1, columns, diagonals1, diagonals2)
		queens[row] = -1
		delete(columns, i)
		delete(diagonals1, diagonal1)
		delete(diagonals2, diagonal2)
	}
}

func generateBoard(queens []int, n int) []string {
	board := []string{}
	for i := 0; i < n; i++ {
		row := make([]byte, n)
		for j := 0; j < n; j++ {
			row[j] = '.'
		}
		row[queens[i]] = 'Q'
		board = append(board, string(row))
	}
	return board
}

func CanQueueNew(queueArrays [][]bool, n, i, j int) bool {
	return false
}

func MarshalQueue(queueArrays [][]bool) []string {
	var res []string

	for _, array := range queueArrays {
		str := ""
		for _, has := range array {
			if has {
				str = str + "Q"
			} else {
				str = str + "."
			}
		}
		res = append(res, str)
	}

	return res
}

// 题目看错了，完蛋
func solveNQueensOld(n int) [][]string {
	// 回溯，记录每一列皇后的位置，暴力回溯
	var res [][]string

	queueArrays := make([][]bool, n)
	for i := range queueArrays {
		queueArrays[i] = make([]bool, n)
	}

	queueNum := 0
	var dfs func(idx int)
	dfs = func(idx int) {
		y := idx / n
		x := idx % n

		if y >= n || n*n-idx < (n-queueNum)*2 {
			return
		}

		dfs(idx + 1)

		if CanQueue(queueArrays, n, x, y) {
			queueNum++
			queueArrays[x][y] = true
			if queueNum == n {
				res = append(res, MarshalQueue(queueArrays))
			} else {
				dfs(idx + 1)
			}
			queueArrays[x][y] = false
			queueNum--
		}
	}

	dfs(0)

	return res
}

func CanQueue(queueArrays [][]bool, n, i, j int) bool {
	// 判定当前位置是不是可以放Q, 从上到下，从左到右回溯，所以可以忽略掉右下的部分
	// left top: i-1, j-1
	if (i-1 >= 0 && i-1 < n) && (j-1 >= 0 && j-1 < n) && queueArrays[i-1][j-1] {
		return false
	}
	// left bottom: i+1, j-1
	if (i+1 >= 0 && i+1 < n) && (j-1 >= 0 && j-1 < n) && queueArrays[i+1][j-1] {
		return false
	}
	// right bottom: i+1, j+1
	if (i+1 >= 0 && i+1 < n) && (j+1 >= 0 && j+1 < n) && queueArrays[i+1][j+1] {
		return false
	}
	// right top: i-1, j+1
	if (i-1 >= 0 && i-1 < n) && (j+1 >= 0 && j+1 < n) && queueArrays[i-1][j+1] {
		return false
	}

	// top: i-1, j
	if (i-1 >= 0 && i-1 < n) && (j >= 0 && j < n) && queueArrays[i-1][j] {
		return false
	}
	// right: i, j+1
	if (i >= 0 && i < n) && (j+1 >= 0 && j+1 < n) && queueArrays[i][j+1] {
		return false
	}
	// bottom: i+1, j
	if (i+1 >= 0 && i+1 < n) && (j >= 0 && j < n) && queueArrays[i+1][j] {
		return false
	}
	// left : i, j-1
	if (i >= 0 && i < n) && (j-1 >= 0 && j-1 < n) && queueArrays[i][j-1] {
		return false
	}
	return true
}

// 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
//
//n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
//
//给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
//
//每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
//
//示例 1：
//
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
//示例 2：
//
//输入：n = 1
//输出：[["Q"]]
//
//提示：
//
//1 <= n <= 9
